// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

// 此文件实现类型参数推断。

package types2

import (
	"bytes"
	"cmd/compile/internal/syntax"
)

const useConstraintTypeInference = true

// 推断尝试推断泛型函数实例化/调用的完整类型参数集
// 基于给定的类型参数tparams、类型参数targets、函数参数params和
// 函数参数args（如果有）。必须至少有一个类型参数，不能有更多的类型参数
// 类型参数，参数和参数的数量必须匹配（包括零）。
// 如果成功，推断将返回类型参数的完整列表，每个类型参数一个。
// 否则，结果为零，除非报告设置为false，否则将报告相应的错误。
// None
// 推理分三步进行：
// None
// 1） 从给定的类型参数开始。
// 2） 从类型化函数参数推断类型参数。
// 3） 从非类型化函数参数推断类型参数。
// None
// 在每个步骤之后使用约束类型推断来扩展类型参数集。
// None
func (check *Checker) infer(pos syntax.Pos, tparams []*TypeName, targs []Type, params *Tuple, args []*operand, report bool) (result []Type) {
	if debug {
		defer func() {
			assert(result == nil || len(result) == len(tparams))
			for _, targ := range result {
				assert(targ != nil)
			}
			// check.dump（“###推断目标=%s”，结果）
		}()
	}

	// 必须至少有一个类型参数，并且类型参数不能多于类型参数。
	n := len(tparams)
	assert(n > 0 && len(targs) <= n)

	// 函数参数和参数的数量必须匹配。
	assert(params.Len() == len(args))

	// --- 0 ---
	// 如果我们已经有了所有类型参数，那么我们就完成了。
	if len(targs) == n {
		return targs
	}
	// len（targs）<n

	// --- 1 ---
	// 显式提供的类型参数优先于任何推断类型；
	// 通过约束类型推断推断出的类型优先于类型
	// 从函数参数推断。
	// 如果我们有类型参数，请查看约束类型推断的进展。
	if len(targs) > 0 && useConstraintTypeInference {
		var index int
		targs, index = check.inferB(tparams, targs, report)
		if targs == nil || index < 0 {
			return targs
		}
	}

	// 继续使用我们现在拥有的类型参数。避免匹配泛型
	// 已具有针对函数参数的类型参数的参数：
	// 它可能会失败，因为在传递参数时匹配使用类型标识
	// 使用分配规则。使用类型实例化参数列表
	// 参数，并继续该参数列表。

	// 首先，确保我们有一个类型参数的“完整”列表，所以
	// 可能为零（未知）。
	if len(targs) < n {
		targs2 := make([]Type, n)
		copy(targs2, targs)
		targs = targs2
	}
	// len（targets）=n

	// 将类型参数替换为参数中各自的类型参数，
	// 如果有的话。请注意，check.subst会忽略nil targs条目。
	// TODO（gri）我们可以避免这种情况吗（我们在下面设置已知类型参数，
	// 但目前这并不影响iParameterized检查）。
	if params.Len() > 0 {
		smap := makeSubstMap(tparams, targs)
		params = check.subst(nopos, params, smap).(*Tuple)
	}

	// --- 2 ---
	// 使用类型化参数统一泛型参数的参数和参数类型
	// 并收集具有非类型参数的泛型参数的索引。
	// 术语：泛型参数=类型参数化类型的函数参数
	u := newUnifier(check, false)
	u.x.init(tparams)

	// 设置我们已经知道的类型参数。
	for i, targ := range targs {
		if targ != nil {
			u.x.set(i, targ)
		}
	}

	errorf := func(kind string, tpar, targ Type, arg *operand) {
		if !report {
			return
		}
		// 如果可以，请提供更好的错误消息
		targs, index := u.x.types()
		if index == 0 {
			// 无法推断第一个类型参数。
			// 如果没有一个是可以推断的，不要尝试
			// 在错误消息中提供推断类型。
			allFailed := true
			for _, targ := range targs {
				if targ != nil {
					allFailed = false
					break
				}
			}
			if allFailed {
				check.errorf(arg, "%s %s of %s does not match %s (cannot infer %s)", kind, targ, arg.expr, tpar, typeNamesString(tparams))
				return
			}
		}
		smap := makeSubstMap(tparams, targs)
		inferred := check.subst(arg.Pos(), tpar, smap)
		if inferred != tpar {
			check.errorf(arg, "%s %s of %s does not match inferred type %s for %s", kind, targ, arg.expr, inferred, tpar)
		} else {
			check.errorf(arg, "%s %s of %s does not match %s", kind, targ, arg.expr, tpar)
		}
	}

	// 带有非类型化参数的泛型参数的索引-保存以备以后使用
	var indices []int
	for i, arg := range args {
		par := params.At(i)
		// 如果我们允许双向统一，这个条件代码需要
		// 即使PAR.TYP没有参数化也可以执行，因为参数可能是
		// 泛型函数（我们想推断它的类型参数）。
		if isParameterized(tparams, par.typ) {
			if arg.mode == invalid {
				// 早些时候报告了一个错误。忽略此目标
				// 继续说下去，我们可能仍然能够推断出所有
				// targs导致更少的后续错误。
				continue
			}
			if targ := arg.typ; isTyped(targ) {
				// 如果我们允许双向统一，targ是
				// 一个泛型函数，我们需要用
				// targ的相应类型参数。
				if !u.unify(par.typ, targ) {
					errorf("type", par.typ, targ, arg)
					return nil
				}
			} else {
				indices = append(indices, i)
			}
		}
	}

	// 如果我们有了所有类型参数，我们就完成了。
	var index int
	targs, index = u.x.types()
	if index < 0 {
		return targs
	}

	// 看看我们在约束类型推断方面取得了多大进展。
	// 注意，即使我们没有任何类型参数，约束类型推断
	// 可以为显式指定类型的约束生成结果。
	if useConstraintTypeInference {
		targs, index = check.inferB(tparams, targs, report)
		if targs == nil || index < 0 {
			return targs
		}
	}

	// --- 3 ---
	// 使用任何非类型化参数推断其他类型参数。
	// 可能已经给出了一些带有非类型参数的泛型参数
	// 到现在为止，我们可以忽略它们。
	for _, i := range indices {
		par := params.At(i)
		// 由于非类型化类型都是基本（即非复合）类型，因此
		// 非类型化参数永远不会与复合参数类型匹配；这个
		// 它可能匹配的唯一参数类型是*TypeParam。
		// 因此，只考虑泛型参数的非类型参数。
		// 不是复合类型，并且尚未推断出类型。
		if tpar, _ := par.typ.(*TypeParam); tpar != nil && targs[tpar.index] == nil {
			arg := args[i]
			targ := Default(arg.typ)
			// 非类型化nil的默认类型为非类型化nil。我们不能这样做
			// 将非类型化的nil类型推断为类型参数类型。忽略非类型化
			// 通过确保所有默认参数类型都已键入，则为nil。
			if isTyped(targ) && !u.unify(par.typ, targ) {
				errorf("default type", par.typ, targ, arg)
				return nil
			}
		}
	}

	// 如果我们有了所有类型参数，我们就完成了。
	targs, index = u.x.types()
	if index < 0 {
		return targs
	}

	// 同样，接下来是约束类型推断。
	if useConstraintTypeInference {
		targs, index = check.inferB(tparams, targs, report)
		if targs == nil || index < 0 {
			return targs
		}
	}

	// 至少有一个类型参数无法推断。
	assert(targs != nil && index >= 0 && targs[index] == nil)
	tpar := tparams[index]
	if report {
		check.errorf(pos, "cannot infer %s (%s) (%s)", tpar.name, tpar.pos, targs)
	}
	return nil
}

// typeNamesString生成一个包含所有
// 在列表中键入适合人类使用的名称。
func typeNamesString(list []*TypeName) string {
	// 常见案例
	n := len(list)
	switch n {
	case 0:
		return ""
	case 1:
		return list[0].name
	case 2:
		return list[0].name + " and " + list[1].name
	}

	// 一般情况（n>2）
	// 希望使用strings.Builder，但它在Go 1.4中不可用。
	var b bytes.Buffer
	for i, tname := range list[:n-1] {
		if i > 0 {
			b.WriteString(", ")
		}
		b.WriteString(tname.name)
	}
	b.WriteString(", and ")
	b.WriteString(list[n-1].name)
	return b.String()
}

// IsParameterized报告typ是否包含tparams的任何类型参数。
func isParameterized(tparams []*TypeName, typ Type) bool {
	w := tpWalker{
		seen:    make(map[Type]bool),
		tparams: tparams,
	}
	return w.isParameterized(typ)
}

type tpWalker struct {
	seen    map[Type]bool
	tparams []*TypeName
}

func (w *tpWalker) isParameterized(typ Type) (res bool) {
	// 检测周期
	if x, ok := w.seen[typ]; ok {
		return x
	}
	w.seen[typ] = false
	defer func() {
		w.seen[typ] = res
	}()

	switch t := typ.(type) {
	case nil, *Basic: // TODO（gri）是否应在此处处理零？
		break

	case *Array:
		return w.isParameterized(t.elem)

	case *Slice:
		return w.isParameterized(t.elem)

	case *Struct:
		for _, fld := range t.fields {
			if w.isParameterized(fld.typ) {
				return true
			}
		}

	case *Pointer:
		return w.isParameterized(t.base)

	case *Tuple:
		n := t.Len()
		for i := 0; i < n; i++ {
			if w.isParameterized(t.At(i).typ) {
				return true
			}
		}

	case *Sum:
		return w.isParameterizedList(t.types)

	case *Signature:
		// t、 如果我们查看签名，tparams可能不是零
		// 泛型函数类型（或接口方法）的
		// 我们正在测试的部分类型。我们不在乎这些类型
		// 参数。
		// 类似地，方法的接收者可以声明（而不是
		// 使用）类型参数，我们也不关心这些。
		// 因此，我们只需要查看输入和结果参数。
		return w.isParameterized(t.params) || w.isParameterized(t.results)

	case *Interface:
		if t.allMethods != nil {
			// 界面完整-快速测试
			for _, m := range t.allMethods {
				if w.isParameterized(m.typ) {
					return true
				}
			}
			return w.isParameterizedList(unpack(t.allTypes))
		}

		return t.iterate(func(t *Interface) bool {
			for _, m := range t.methods {
				if w.isParameterized(m.typ) {
					return true
				}
			}
			return w.isParameterizedList(unpack(t.types))
		}, nil)

	case *Map:
		return w.isParameterized(t.key) || w.isParameterized(t.elem)

	case *Chan:
		return w.isParameterized(t.elem)

	case *Named:
		return w.isParameterizedList(t.targs)

	case *TypeParam:
		// t必须是w.t图形之一
		return t.index < len(w.tparams) && w.tparams[t.index].typ == t

	case *instance:
		return w.isParameterizedList(t.targs)

	default:
		unreachable()
	}

	return false
}

func (w *tpWalker) isParameterizedList(list []Type) bool {
	for _, t := range list {
		if w.isParameterized(t) {
			return true
		}
	}
	return false
}

// inferB返回从类型参数的
// 边界和类型参数的初始集。如果类型推断是不可能的，因为
// 统一失败，如果报告设置为true，则报告错误，结果类型为
// 列表为零，索引为0。
// 否则，类型是推断类型参数的列表，索引是
// 该列表中无法推断的第一个类型参数（因此为nil）。如果有的话
// 已成功推断类型参数，索引<0。类型参数的数目
// 提供的类型参数可能少于类型参数的数量，但必须至少有一个。
func (check *Checker) inferB(tparams []*TypeName, targs []Type, report bool) (types []Type, index int) {
	assert(len(tparams) >= len(targs) && len(targs) > 0)

	// 在这些结构边界之间设置双向统一
	// 以及相应的类型参数（可能为零！）。
	u := newUnifier(check, false)
	u.x.init(tparams)
	u.y = u.x // 统一的LHS和RHS之间的类型参数相同

	// 设置我们已经知道的类型参数。
	for i, targ := range targs {
		if targ != nil {
			u.x.set(i, targ)
		}
	}

	// 统一类型参数及其结构约束（如果有）。
	for _, tpar := range tparams {
		typ := tpar.typ.(*TypeParam)
		sbound := check.structuralType(typ.bound)
		if sbound != nil {
			if !u.unify(typ, sbound) {
				if report {
					check.errorf(tpar, "%s does not match %s", tpar, sbound)
				}
				return nil, 0
			}
		}
	}

	// u、 x.types（）现在包含传入的类型参数和任何其他类型
	// 存在结构性约束的参数。新推断的非-
	// nil条目可能仍然包含对其他类型参数的引用。例如，
	// 对于[A any，B接口{type[]C}，C接口{type*A}]，如果A==int
	// 统一生成了类型列表[int，[]C，*A]。我们消除了
	// 通过替换此类型列表中的类型参数来保留其他类型参数
	// 直到一切不再改变。
	types, _ = u.x.types()
	if debug {
		for i, targ := range targs {
			assert(targ == nil || types[i] == targ)
		}
	}

	// 脏跟踪可能仍包含类型参数的所有类型的索引。
	// 我们知道提供了nil类型的条目和对应的条目（非nil）
	// 类型参数是干净的，所以从一开始就排除它们。
	var dirty []int
	for i, typ := range types {
		if typ != nil && (i >= len(targs) || targs[i] == nil) {
			dirty = append(dirty, i)
		}
	}

	for len(dirty) > 0 {
		// TODO（gri），而不是为每个迭代创建新的子映射，
		// 为子映射提供更新操作，仅在
		// 需要。优化。
		smap := makeSubstMap(tparams, types)
		n := 0
		for _, index := range dirty {
			t0 := types[index]
			if t1 := check.subst(nopos, t0, smap); t1 != t0 {
				types[index] = t1
				dirty[n] = index
				n++
			}
		}
		dirty = dirty[:n]
	}

	// 一旦不再有任何变化，我们可能仍然保留类型参数；
	// e、 例如，结构约束*P可能与类型参数Q匹配，但我们
	// 对于*P或Q（问题#45548），没有任何类型参数需要填写。
	// 不要让这样的推论漏掉，相反，要把它们抹掉。
	for i, typ := range types {
		if typ != nil && isParameterized(tparams, typ) {
			types[i] = nil
		}
	}

	// 更新索引
	index = -1
	for i, typ := range types {
		if typ == nil {
			index = i
			break
		}
	}

	return
}

// StructureType返回约束的结构类型（如果有）。
func (check *Checker) structuralType(constraint Type) Type {
	if iface, _ := under(constraint).(*Interface); iface != nil {
		check.completeInterface(nopos, iface)
		types := unpack(iface.allTypes)
		if len(types) == 1 {
			return types[0]
		}
		return nil
	}
	return constraint
}
